package william.array;

/**
 * @author ZhangShenao
 * @date 2024/4/8
 * @description <a href="https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 */
public class Leetcode560_和为k的子数组 {
    /**
     * 采用前缀和数组实现
     * 构造前缀和数组preSum,preSum[i]即为数组[0,i]部分的和
     * 计算有多少个[left,right]区间的子数组和==k,即为计算有多少个preSum[right]-preSum[left-1]==k
     * <p>
     * 时间复杂度O(N^N)
     * 空间复杂度O(N) 额外申请了一个前缀和数组,长度为N
     */
    public int subarraySum(int[] nums, int k) {
        //边界条件校验
        if (nums == null || nums.length < 1) {
            return 0;
        }

        int N = nums.length;

        //构造前缀和数组
        int[] preSum = new int[N];
        preSum[0] = nums[0];
        for (int i = 1; i < N; i++) {
            preSum[i] = preSum[i - 1] + nums[i];
        }

        int count = 0;
        for (int right = 0; right < N; right++) {
            for (int left = 0; left <= right; left++) {
                if (left == 0) {
                    if (preSum[right] == k) {
                        count++;
                    }
                } else {
                    if (preSum[right] - preSum[left - 1] == k) {
                        count++;
                    }
                }
            }
        }

        //返回结果
        return count;

    }
}
